Linear transformation consists of rotation, scaling, anamorphic distortion, and shearing. Interpolation is smoothing the transitions between pixels, while screening is the preparation of continuous tone images into bilevel halftones composed of dots. Halftone screening allows continuous tone images to be printed on typical printing devices where the absence or presence of the ink on the paper is used to represent the printed image. In order to represent halftones (shades between the presence or absence of the printed ink), the original image is screened to produce a pattern, such a variable size dots which appear to the human eye as a halftone image. Thus, screening tends to increase the number of output image pixels as compared to the original input image. In general, the larger number of pixels in an image increases the burden of image processing hardware and software, making processing speed per pixel a critical system limitation.
In a copending patent application, Ser. No. 748,948, filed Aug. 23, 1991 to the present inventor, entitled "HIGH SPEED SCREENING OF IMAGES", a system and method is disclosed for generating microcode for enlarging an image by any desired enlargement ratio, and combining the enlarged image with a halftone screen cell to produce a halftone screened image. The enlargement process and halftone screening steps are combined in a continuous efficient process to produce a halftone image output. However, in addition to enlarging and screening an image, it is often desirable to be able to rotate the image to any desired angle.
Image rotation techniques are well known. In one prior art direct approach, a new location is calculated for each pixel by appropriate trigonometric function, thereby rotating the image through the desired angle. However, the direct calculation approach is much too slow for use in screening stored images in which each output pixel is computed from a scanned input image as the source image. Direct calculation of a rotated image can require several seconds per image scan line.
In another technique, known in the prior art, image rotation is achieved by skewing the image in the horizontal direction (along the X axis), and then skewing the image in the vertical direction (along the Y axis). However, skewing tends to produce jagged line edges, like a staircase. To smooth the transitions between pixels of the rotated image, interpolation is used to add pixels to the rotated image. Thus, in addition to the two skew operations, the image is scaled and interpolated in both the X and Y directions. Scaling and interpolation are computationally costly steps, particularly when performed in the vertical direction, thereby slowing the image screening process. Also, if interpolation is performed before Y skew, then many more data points must be processed, which slows down image processing speed. On the other hand, having more data points is desirable in that it reduces the reduces the step size of the jagged stair steps resulting from Y skew.
Interpolation also dramatically reduces the jagged pixel edges that are apparent in many digital halftones, as well as helping to prevent ragged and broken dots, also known as "moon crater dots" in the final screened halftone, which can result when a halftone dot straddles a high contrast pixel transition. The process of interpolation is well known to those skilled in the art of digital signal processing. In effect, interpolation increases the effective sampling rate of input data by fitting the best curve to the data with frequencies below the Nyquist limit.